package list;

public class LeetCode234 {
    /**
     * 反转链表再做比较需要额外的空间保存反转后的链表
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head) {
        if (head == null || head.next ==null) return true;
        ListNode reverse = reverseList(head);
        ListNode p1 = head;
        ListNode p2 = reverse;

        while (p1 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }


    public ListNode reverseList(ListNode head) {
        ListNode p = head;
        ListNode res = null;

        while (p != null) {
            res = new ListNode(p.val, res);
            p = p.next;
        }
        return res;
    }


    /**
     * 使用递归方式解决
     */
    ListNode temp;

    public boolean isPalindrome(ListNode head) {
        temp = head;
        return check(head);
    }

    public boolean check(ListNode head) {
        if (head != null) {
            boolean res = check(head.next);
            if (head.val != temp.val) {
                res = false;
            }
            temp = temp.next;
            return res;
        } else {
            return true;
        }
    }
}
